#!/usr/bin/env python
# -*- coding: utf-8 -*-

# @Time     :2020/12/10
# @Author   :Changshu
# @File     :Exercise_559.py

# 559. N 叉树的最大深度
# 给定一个 N 叉树，找到其最大深度。
#
# 最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。
#
# N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。


class Node:
	def __init__(self, val=None, children=None):
		self.val = val
		self.children = children

'''深度优先，递归
class Solution:
	def maxDepth(self, root: Node) -> int:
		if root is None:
			return 0
		if not root.children:
			return 1
		height=[self.maxDepth(n) for n in root.children]
		return max(height)+1
'''

'''非递归，迭代法'''
class Solution:
	def maxDepth(self, root: Node) -> int:
		stack=[]
		if root is not None:
			stack.append((1,root))
		depth=0
		while stack:
			curDepth,node=stack.pop()
			if node:
				depth=max(depth,curDepth)
				for n in node.children:
					stack.append((curDepth+1,n))
		return depth
